package com.cty.ThirtyFirstDay;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。
* */
public class Q_51 {

    // 主包自己写的过了奥 时间复杂度O(M * N) 空间复杂度O(M * N) 深度优先搜索
    int ans = 0;

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (grid[i][j] == '1') {
                    dfs(grid, visited, i, j);
                    ans++;
                } else {
                    visited[i][j] = true;
                }
            }
        }
        return ans;
    }

    public void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        visited[x][y] = true;
        if (grid[x][y] == '0') {
            return;
        }
        if (y + 1 < grid[0].length && !visited[x][y + 1]) {
            dfs(grid, visited, x, y + 1);
        }
        if (x + 1 < grid.length && !visited[x + 1][y]) {
            dfs(grid, visited, x + 1, y);
        }
        if (y - 1 >= 0 && !visited[x][y - 1]) {
            dfs(grid, visited, x, y - 1);
        }
        if (x - 1 >= 0 && !visited[x - 1][y]) {
            dfs(grid, visited, x - 1, y);
        }
    }

    // 主包用bfs写一个 试一下 过了但是效率不高 时间复杂度O(MN) 空间复杂度O(MN)
    public int numIslands2(char[][] grid) {
        int[] direction = new int[2];
        // 创建一个队列
        Queue<int[]> queue = new LinkedList<>();
        int ans = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (grid[i][j] == '1') {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        int[] poll = queue.poll();
                        int x = poll[0];
                        int y = poll[1];
                        if (y + 1 < grid[0].length && !visited[x][y + 1]) {
                            if (grid[x][y + 1] == '1') {
                                queue.offer(new int[]{x, y + 1});
                            }
                            visited[x][y + 1] = true;
                        }
                        if (x + 1 < grid.length && !visited[x + 1][y]) {
                            if (grid[x + 1][y] == '1') {
                                queue.offer(new int[]{x + 1, y});
                            }
                            visited[x + 1][y] = true;
                        }
                        if (y - 1 >= 0 && !visited[x][y - 1]) {
                            if (grid[x][y - 1] == '1') {
                                queue.offer(new int[]{x, y - 1});
                            }
                            visited[x][y - 1] = true;
                        }
                        if (x - 1 >= 0 && !visited[x - 1][y]) {
                            if (grid[x - 1][y] == '1') {
                                queue.offer(new int[]{x - 1, y});
                            }
                            visited[x - 1][y] = true;
                        }
                    }
                    ans++;
                }
                visited[i][j] = true;
            }
        }
        return ans;
    }


    // 力扣官方题解 方法一: dfs
    /*
     * 思路:
     *   用深度优先搜索 只不过不用访问标识数组 而是将当前
     *   输入数组值置为0，非常的牛逼
     *   时间复杂度O(MN) 空间复杂度O(MN) 最坏情况(全部都是陆地) 因为递归用到了栈
     * */
    public int numIslands3(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int ans = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    public void dfs(char[][] grid, int row, int col) {
        if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) {
            return;
        }
        if (grid[row][col] == '0') {
            return;
        }
        // 将当前的元素置为'0' 表示已经被访问过
        grid[row][col] = '0';
        dfs(grid, row, col + 1);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row - 1, col);
    }

    //力扣官方题解 bfs
    /*
     * 思路:
     *   也是不用标识数组 将访问过且为'1'的元素赋值为'0'
     *   加入队列
     * */
    public int numIslands4(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rl = grid.length;
        int cl = grid[0].length;
        int ans = 0;
        for (int i = 0; i < rl; i++) {
            for (int j = 0; j < cl; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    Queue<Integer> queue = new LinkedList<>();
                    queue.offer(i * cl + j);
                    grid[i][j] = '0';
                    while (!queue.isEmpty()) {
                        Integer poll = queue.poll();
                        int row = poll / cl;
                        int col = poll % cl;
                        if (col + 1 < cl && grid[row][col + 1] == '1') {
                            queue.offer(row * cl + col + 1);
                            grid[row][col + 1] = '0';
                        }
                        if (row + 1 < rl && grid[row + 1][col] == '1') {
                            queue.offer((row + 1) * cl + col);
                            grid[row + 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            queue.offer(row * cl + col - 1);
                            grid[row][col - 1] = '0';
                        }
                        if (row - 1 >= 0 &&grid[row - 1][col] == '1'){
                            queue.offer((row-1) * cl + col);
                            grid[row - 1][col] = '0';
                        }
                    }
                }
            }
        }
        return ans;
    }
}
